#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstdlib>
#include <omp.h>
#include <time.h>

#include "rdtsc.h"

using namespace std;

struct Path
{
  bool exist;
  int weight;

  // Make no existing path by default
  Path()
  {
    exist   = false;
    weight  = 0;
  }
};

struct PathF
{
  bool exist;
  int weight;
  vector <unsigned int> path;

  PathF()
  {
    exist   = false;
    weight  = 0;
  }
};

class Graph
{
  Path ** G;    // Adjacency matrix of not complete graph
  PathF ** Gf;  // Adjacency matrix of complet graph

  int N;        // Nodes
  int P;        // Pathes

  public:
  Graph();
  Graph(char * nazwa);
  ~Graph();

  void allocation(int n);
  void deallocation();
  bool isData();
  bool read(char * filename);
  void compute();
  void floydWarshall();
  void findPaths();
  void findPath(int start, int meta);
  vector<int> antecedents(int x);
  void show();
  void showFull();
  void showShortesPaths();
};

Graph::Graph()
{
  P = 0;
  N = 0;
}

Graph::Graph(char * filename)
{
  N = 0;
  P = 0;
  read(filename);
}

Graph::~Graph()
{
  deallocation();
}

void Graph::allocation(int n)
{
  if ( isData() )
  {
    deallocation();
  }

  N = n;

  G = new Path * [N];
  Gf = new PathF * [N];

  for (int i = 0; i < N; ++i)
  {
    G[i] = new Path[N];
    Gf[i] = new PathF[N];

    // Diagonal
    G[i][i].exist = true;
    Gf[i][i].exist = true;
  }
}

void Graph::deallocation()
{
  if ( isData() )
  {
    for ( int i = 0; i < N; ++i )
    {
      delete [] G[i];
      delete [] Gf[i];
    }

    delete [] G;
    delete [] Gf;
  }
}

bool Graph::isData()
{
  if ( N > 0 )  return true;
  else          return false;
}

/* Method to reading data from file.
 * File structure:
 * nodes  paths
 * from to  weight
 *
 * Example:
 * 2  1
 * 0  1 10
 *
 * Means that graph has two nodes, and one path
 * from node 0 to node 1 and this path has weight
 * equal 10.
 */
bool Graph::read(char * filename)
{
  ifstream file(filename, ifstream::in);
 
  if ( file.is_open() )
  {
    int n;

    file >> n >> P;

    allocation(n);
   
    // Reading file
    int x, y, w;        // tmp vars
   
    for (int i = 0; i < P; ++i)
    {
      file >> x >> y >> w;
      G[x - 1][y - 1].exist = true;
      G[x - 1][y - 1].weight = w;

      Gf[x - 1][y - 1].exist = true;
      Gf[x - 1][y - 1].weight = w;
    }


    return true;
  }

  return false;
}

void Graph::compute()
{
  floydWarshall();
  findPaths();
}

// Finding all-pairs shortest paths on a graph
void Graph::floydWarshall()
{
  for ( int k = 0; k < N; ++k )
  {
    for ( int i = 0; i < N; ++i )
    {
      for ( int j = 0; j < N; ++j )
      {
        if ( Gf[i][k].exist && Gf[k][j].exist )
        {
          if ( !Gf[i][j].exist )
          {
            Gf[i][j].weight = Gf[i][k].weight + Gf[k][j].weight;
          }

          else
          {
            Gf[i][j].weight = min(Gf[i][j].weight, Gf[i][k].weight + Gf[k][j].weight);
          }

          Gf[i][j].exist = true;
        }
      }
    }
  }
}


void Graph::findPaths()
{
  int i, j, id, n_thr;
  int max = N;
  n_thr = 2;    //ilosc watkow
 
  //default(none) - domyslnie zadna zmienna nie bedzie ani prawatna ani wspolna
  //private (i,j) - kazdy watek bedzie mial wlasny licznik iteracji
  //schered(max) - zmienna wspolna

  //#pragma omp parallel default(none) shared(max) private(i,j,id)
  //{
    #pragma omp single
    {
      //printf("Program jest wykonywany na %d watkach.\n", omp_get_num_threads());
    }
 
  //schedule(static) - kazdy watek dostaje w przyblizeniu (liczba_iteracji/liczba_watkow) iteracji
  //mozna stestowac tez dla 'dynamic', 'guided' i 'runtime'
  //if() num_threads() - jesli warunek jest niespelniony, wtedy program wykonuje sie sekwencyjnie
    #pragma omp parallel for schedule(static)\
	 if(max > 20) num_threads(n_thr)\
	default(none) shared(max) private(i,j,id)
    for ( i = 0; i < max; ++i )
    {
      for ( j = 0; j < max; ++j )
      {
        id = omp_get_thread_num();
        //printf("Iteracja dla (%d,%d) wykonana przez watek nr. %d.\n", i, j, id);
        findPath(i, j);
      }
    }
  //}
}

void Graph::findPath(int start, int meta)
{
  if ( !Gf[start][meta].exist )
  {
    return;
  }

  vector<int> ant;    // Antecedents
  stack<int> path;  // Path from start to meta
  int u, v;         // Tmp vars

  path.push(meta);
  v = meta;

  while ( v != start )
  {
    ant = antecedents(v);

    if ( ant.empty() )
    {
      break;
    }

    for ( unsigned int i = 0; i < ant.size(); ++i )
    {
      if ( Gf[start][v].weight == Gf[start][ant[i]].weight + G[ant[i]][v].weight )
      {
        u = ant[i];
      }
    }

    path.push(u);
    v = u;
  }

  // Copy stack to path in PathF structure
  while ( !path.empty() )
  {
    Gf[start][meta].path.push_back(path.top());
    path.pop();
  }
}

vector<int> Graph::antecedents(int x)
{
  vector<int> ants;

  for ( int i = 0; i < N; ++i )
  {
    if ( G[i][x].exist && G[i][x].weight != 0 )
    {
      ants.push_back(i);
    }
  }

  return ants;
}

void Graph::show()
{
  for ( int i = 0; i < N; ++i )
  {
    for ( int j = 0; j < N; ++j )
    {
      cout << G[i][j].weight << " ";
    }

    cout << endl;
  }
}

void Graph::showFull()
{
  for ( int i = 0; i < N; ++i )
  {
    for ( int j = 0; j < N; ++j )
    {
      cout << Gf[i][j].weight << " ";
    }

    cout << endl;
  }
}

void Graph::showShortesPaths()
{
  for ( int i = 0; i < N; ++i )
  {
    for ( int j = 0; j < N; ++j )
    {
      if ( i != j )
      {
        cout << "Shortes path from: " << i << " to: " << j << " weight: " << Gf[i][j].weight << ". Path: ";

        for ( unsigned int k = 0; k < Gf[i][j].path.size(); ++k )
        {
          cout << Gf[i][j].path[k] << ", ";
        }

        cout << endl;
      }
    }
  }
}

int main(int argc, char * argv[])
{
  if ( argc == 1 )
  {
    cout << "Give path to file with graph" << endl;
    cout << "Example:" << endl;
    cout << argv[0] << " dane_przykladowe.txt" << endl;

    exit(0);
  }

  Graph G(argv[1]);
  Rdtsc t;

  t.start();

  for ( int i = 0; i < 500; ++i )
  {
    G.compute();
  }

  t.stop();

//  G.show();
//  G.showShortesPaths();
 
  return 0;
}
